In traditional circuit switching (also called Synchronous Transfer Mode, or STM switching), scheduler frames of fixed length are used to schedule the transmission of voice traffic across network links. A scheduler frame is a time-space map residing in a switch's control apparatus. Each of its entries specifies a predefined connection that has data units queued for transmission over a given link. The position of each entry within the scheduler frame relates to a unique window of time during which one of those units will be transmitted out over the link, and is thus referred to as a time-slot. After a link controller reads in a connection identifier from one of the scheduler frame's time-slots, it will transmit a data unit belonging to that connection, at a time specified by the position of the time-slot within the frame.
In circuit switched voice networks, the data unit associated with each time-slot is typically one byte. Because a frame is scanned 8000 times per second, the rate at which each user is served is 8000 bytes/second, or an integer multiple thereof if the user is allotted more than one slot per frame. Time-slots are updated with new connection identifiers as new connections are created and torn down. In circuit switching, one can thus control the order in which various connections will be served (that is, the order in which the buffered data units of each connection are transmitted out over the link) by controlling the sequence of the contents of each link's scheduler frame. One can likewise control the rates at which each given connection will be served by controlling the number of time-slots that the connection is allocated within each frame.
At least three benefits accrue to users of these simple STM scheduler frames used in circuit switching. The first benefit is that there are never any collisions in the scheduler frame between two connections wishing to use the same time-slot. This is because a fixed-allocation scheme is used, meaning each connection always gets not only the same number of time-slots per frame, but the very same time-slots within a frame, for each frame-cycle. Collisions are undesirable because they require that the switch allocate computing power to resolve the collision situation, resulting in reduced throughput. The second benefit associated with STM scheduler frames is that the variance of each connection's sampling interval, which is the length of time that elapses between the start of successive samples of a connection's data units, is zero. This means that the switch is not transmitting bursts of consecutive or almost consecutive data units belonging to the same connection, but rather is transmitting each connection's units at consistently-spaced intervals of time. Such transmissions are said to have zero delay-jitter and are highly desirable when dealing with delay-sensitive data that must be switched in a timely manner. The third benefit associated with STM scheduler frames stems from the operational and implementational simplicity associated with these fixed-size frames.
In light of the aforementioned benefits, it is desirable to adapt the simple and robust STM scheduler frames to schedule the transmission of ATM streams, which consist of one or more virtual circuits (VCs) and/or virtual paths (VPs), that share similar quality of service (QOS) requirements. Such fixed-size and fixed-allocation scheduler frames have yet to be used to handle ATM streams, which are received at arbitrary time-varying bit rates. This is because the use of traditional STM scheduler frames in ATM networks tends to result in wasted link capacity, especially if streams that have been assigned time-slots do not always have data to transmit. Using the STM frames to schedule ATM transmissions may also make it impossible to accommodate streams requiring bit-rates that are not integer multiples of the frame rate. Both shortcomings are significant when switching ATM streams and, as a result, variable length and/or variable-allocation frames have been typically used in many current ATM networks.
Many attempts have been made to overcome these shortcomings, in order to allow switches to manage the time-variant rates in ATM switching using frames that resemble the fixed-size, fixed-allocation frames used by STM switches. More particularly, one of the broad approaches to this challenge involves calculating a carefully selected equivalent bit-rate (EBR) at which to serve an ATM stream and thereafter treating the stream as though it were an STM connection. Under this approach, each time-slot would be set to represent the period of time required to transmit one complete ATM cell, and each ATM stream would be allocated a fixed given number of time-slots, within a scheduler frame, based on the stream's calculated EBR. Then, the scheduling apparatus would work by giving each stream its allocated number of time-slots per frame-cycle, so that ATM traffic is scheduled much like STM traffic.
A simple variant of a scheduler implementation, for example, is the weighted round-robin method of scheduling the transmission of cells. Consider a link which is shared by K streams. A scheduler controlling this link's utilization would assign to each of the K streams a number of time-slots x.sub.0,x.sub.1, . . . x.sub.(K-1), where x.sub.N is the maximum number of slots in a single frame that could be allocated to a stream, N (x.sub.N is based on the calculated EBR for stream N). The scheduler frame thus has a size of x.sub.0 +x.sub.1 + . . . +x.sub.(K-1) time-slots when all the streams have cells to transmit. At the start of each frame-cycle, the streams are polled in a round-robin fashion. If a stream, J, has no cells to transmit, it gets no slots. If J has cells to transmit, it is granted the number of slots it requires up to a predetermined maximum x.sub.J. Entries denoting stream J are then placed into x.sub.J contiguous slots in the frame. The next stream, stream (J+1) modulo K, is then polled and the process is repeated. Under this scheme, time-variant service rates can be supported unlike the situation under an STM scheme, and no bandwidth is wasted as slots are allocated only to streams that need them. Under the round robin scheme however, as the number of streams supported by the scheduler increases, the variance of each stream's sampling interval increases. This leads to intolerable levels of delay-jitter. Consequently, the weighted round-robin scheduler does not provide a workable solution to the challenge of using simple and robust STM scheduler frames to control the transmission of ATM traffic.
Nonetheless, the weighted round-robin scheme can form the basis of more involved implementations. Many such implementations try to reduce delay-jitter by preventing the elapsed time between two consecutive departures of cells belonging to the same stream from exceeding the maximum allowable cell delay variation (CDV) for that stream (see U.S. Pat. No. 5,602,830 for example). This solution is achieved by calculating a theoretical preferred time of transmission for each incoming cell, converting that time into a preferred frame slot number in the frame, and then searching the frame for the nearest available slot to the preferred slot. The problem with such implementations is that they can cause scheduling collisions between streams. As mentioned previously, collisions require a scheduler to engage in many complex operations in order to determine which stream should prevail, and in order to allow streams that do not get their ideal slot to still meet their service requirements (see U.S. Pat. No. 5,602,830 for example). However, the more complex these operations, the longer they take to run, and the longer the frame access-time. So even these alternative implementations currently suffer from inherent limitations.